package com.mrzhou.study.struct.stack;

/**
 * 使用双向链表实现stack
 */
public class LinkedStack<T> {

    private Node<T> top;

    /**
     * 压栈操作
     */
    public void push(T elem) {
        Node<T> node = new Node<T>(elem, top, null);
        if(!isEmpty()) {
            top.next = node;
        }
        top = node;
    }

    public T pop() {
        if(isEmpty()) {
            return null;
        }
        T elem = this.top.elem;
        this.top = this.top.pre;;
        return elem;
    }

    public static void main(String[] args) {
        LinkedStack<String> stack = new LinkedStack<>();
        stack.push("2344");
        stack.push("2345");
        stack.pop();
        stack.pop();
        System.out.println(stack.pop());
    }


    public boolean isEmpty() {
        return top == null;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("[");
        if(isEmpty()) {
            return sb.append(" ]").toString();
        }
        Node<T> current = this.top;
        while(current.pre != null) {
            sb.append(current.elem).append(", ");
            current = current.pre;
        }
        return sb.append(current.elem).append("]").toString();
    }

    private class Node<T> {
        T elem; // 链表节点保存的元素
        Node<T> pre; // 当前节点的上一个节点的指针
        Node<T> next; // 当前节点的下一个节点的指针

        Node(T elem, Node<T> pre, Node<T> next) {
            this.elem = elem;
            this.pre = pre;
            this.next = next;
        }

        public String toString() {
            if(elem == null) {
                return "";
            }
            return elem.toString();
        }

    }

}
